package array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import search.BinarySearch;

public class Intersection {

	// returns intersection of two sorted arrays
	public static int[] intersection(int[] a, int[] b){
		int aLen = a.length;
		int bLen = b.length;
		
		// find min of "aLen + bLen", "aLen x (log bLen)" and "bLen x (log aLen)"
		// in order to find the fastest approach for a given input
		int min1 = aLen + bLen;
		int min2 = (int)(aLen*((Math.log(bLen))/(Math.log(2))));
		int min3 = (int)(bLen*((Math.log(aLen))/(Math.log(2))));
		
		//System.out.println("min1: "+min1);
		//System.out.println("min2: "+min2);
		//System.out.println("min3: "+min3);
		
		int min = min2 > min3 ? min3 : min2;
		min = min > min1 ? min1 : min;
		
		// call the search based on min value
		if(min == min1){
			//System.out.println("min1");
			return linearSearch(a, b);
		}if(min == min2){
			//System.out.println("min2");
			return binarySearch(a, b);
		}else{
			//System.out.println("min3");
			return binarySearch(b, a);
		}
	}

	
	// linear search with complexity O(aLen + bLen)
	private static int[] linearSearch(int[] a, int[] b){
		Set<Integer> intersectionSet = new HashSet<Integer>();
		
		int aIndex = 0;
		int bIndex = 0;
		
		while(aIndex < a.length && bIndex < b.length){
				if(a[aIndex] < b[bIndex]){
					aIndex++;
				}else if(a[aIndex] > b[bIndex]){
					bIndex++;
				}else{
					intersectionSet.add(a[aIndex]);
					aIndex++;
					bIndex++;
				}
		}
		
		// convert Set<Integer> to int[]
		return convertSetToIntArray(intersectionSet);
	}
	

	// binary search with complexity O(a1Len * log(a2Len))
	private static int[] binarySearch(int[] a1, int[] a2){

		Set<Integer> intersectionSet = new HashSet<Integer>();
		
		for(int i : a1){
			if(BinarySearch.search(a2, i) != -1){
				intersectionSet.add(i);
			}
		}
		
		// convert Set<Integer> to int[]
		return convertSetToIntArray(intersectionSet);
	}
	

	// helper method to convert Set<Integer> into int[]
	private static int[] convertSetToIntArray(Set<Integer> intersectionSet){
		int[] intersection = new int[intersectionSet.size()];
		int index = 0;
		for(int i : intersectionSet){
			intersection[index++] = i;
		}
		
		Arrays.sort(intersection); // as set doesn't maintain order
		return intersection;
	}
	
}
